﻿// 4866. 最大数量.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/4869/

一个无向图有 n
 个点，编号 1∼n
。

这些点之间没有任何边。

给定 d
 个需求，编号 1∼d
。

其中，第 i
 个需求是让点 xi
 和点 yi
 连通。

需求可能存在重复。

在本题中，你需要依次解决 d
 个问题，编号 1∼d
。

其中，第 i
 个问题是，请你在图中添加恰好 i
 条无向边（不能添加重边和自环），使得：

前 i
 个需求都得到满足。
所有点中度最大的点的度尽可能大。
对于每个问题，你不需要输出具体方案，你只需要输出度的最大可能值。

注意：

如果点 a
 和点 b
 之间存在路径，则称点 a
 和点 b
 连通。
图中与点 a
 关联的边数，称为点 a
 的度。（如果一个点是一条边的端点，则称这个点和这条边关联）
d
 个问题之间是相互独立的，每个问题的答案都必须独立计算。
输入格式
第一行包含两个整数 n,d
。

接下来 d
 行，其中第 i
 行包含两个整数 xi,yi
，表示第 i
 个需求是让点 xi
 和点 yi
 连通。

输出格式
共 d
 行，其中第 i
 行输出第 i
 个问题中，度的最大可能值。

数据范围
前三个测试点满足，2≤n≤10
。
所有测试点满足，2≤n≤1000
，1≤d≤n−1
，1≤xi,yi≤n
，xi≠yi
。

输入样例1：
7 6
1 2
3 4
2 4
7 6
6 5
1 7
输出样例1：
1
1
3
3
3
6
输入样例2：
10 8
1 2
2 3
3 4
1 4
6 7
8 9
8 10
1 4
输出样例2：
1
2
3
4
5
5
6
8
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 